package com.gzl.exercise;

import org.junit.jupiter.api.Test;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 移动零
 * @DESCRIPTION: 简单
 * @USER: gaozengliang
 * @DATE: 2023/3/28
 */
public class 移动零 {
    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     *
     * 示例 1:
     * 输入: nums = [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     *
     * 示例 2:
     * 输入: nums = [0]
     * 输出: [0]
     *
     * 提示:
     * 1 <= nums.length <= 104
     * -231 <= nums[i] <= 231 - 1
     *
     * 进阶：你能尽量减少完成的操作次数吗？
     */

    // 将 0 移动到数组末尾，每移动一次就需要整个数组的改变，所以反过来，把 非0 的移动到前面，这样只需要调换 0 和 非0 的位置即可

//    优化
//    一：两次遍历，把非零的全部移到前面，剩下的全部赋值为 0
    @Test
    void moveZeroes3(){
        int changeNum = 0;
//        int nums[] = {4,2,4,0,0,3,0,5,1,0}; //预期 4,2,4,3,5,1,0,0,0,0
        int nums[] = {4,2,4,0,0,3,0,5,1,1};
//        int nums[] = {0,1,0,3,12};
//        int nums[] = {0};
        int n = nums.length;

        if (n<2){
            return;
        }

        int move = 0;
        for (int i=0;i<n;i++){
            if (nums[i] != 0){
                if (move!=i){
                    nums[move] = nums[i];
                    changeNum++;
                }
                move++;
            }
        }

        for (int i=move;i<n;i++){
            nums[i] = 0;
        }

        System.out.println(changeNum);
        for (int i=0;i<n;i++){
            System.out.print(nums[i]+",");
        }
    }

//    二：一次遍历，记录零的坐标，交换
    @Test
    void moveZeroes2(){
        int changeNum = 0;
        int nums[] = {4,2,4,0,0,3,0,5,1,0}; //预期 4,2,4,3,5,1,0,0,0,0
//        int nums[] = {0,1,0,3,12};
//        int nums[] = {0};
        int n = nums.length;

        if (n<2){
            return;
        }

        int move = 0;
        for (int i=0;i<n;i++){
            if (nums[i] != 0){
                if (move!=i){
                    int temp = nums[i];
                    nums[i] = 0;
                    nums[move] = temp;
                    changeNum++;
                }
                move++;
            }
        }

        System.out.println(changeNum);
        for (int i=0;i<n;i++){
            System.out.print(nums[i]+",");
        }
    }

    @Test
    void moveZeroes1(){
        int changeNum = 0;
        int nums[] = {4,2,4,0,0,3,0,5,1,0}; //预期 4,2,4,3,5,1,0,0,0,0
//        int nums[] = {0,1,0,3,12};
//        int nums[] = {0};
        int n = nums.length;

        if (n<2){
            return;
        }

        int move;
        for (int i=0;i<n;i++){
            if (nums[i] != 0){
                move = nums[i];
                for (int k=0;k<n;k++){
                    if (k >= i){
                        break;
                    }
                    if (nums[k]==0){
                        nums[k] = move;
                        nums[i] = 0;
                        changeNum++;
                        break;
                    }
                }
            }
        }

        System.out.println(changeNum);
        for (int i=0;i<n;i++){
            System.out.print(nums[i]+",");
        }
    }
}
